package com.wss.lsl.test.driven.arithmetic.sort;

/**
 * 插入排序算法
 * 
 * @author weiss
 */
public class InsertionSort {

	public static int[] sort(int[] data) {
		if (data.length <= 1) {
			return data;
		}

		for (int i = 1; i < data.length; i++) {
			int j = i - 1;
			int key = data[i];
			while (j >= 0 && data[j] > key) {
				int temp = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
				j--;
			}
			data[j + 1] = key;
		}

		return data;
	}
	
	
	public static void recursion(int[] data, int sorted, int next) {
		if(sorted >= data.length) {
			return;
		}
		
		int key = data[next];
		int j = next - 1;
		while(j >= 0 &&  data[j] > key) {
			int temp = data[j];
			data[j] = data[j+1];
			data[j+1] = temp;
			j--;
		}
		data[j + 1] = key;
		
		recursion(data, sorted + 1, next + 1);
	}

}
